use std::str::Chars;
use std::collections::HashMap;

#[allow(dead_code)]
enum Token{
    LP,
    RP,
    PLUS,
    STAR,
    DIGIT,
    LETTER,
    SPACE,
    SPLIT,
    QUESTION,
    CHAR(char),
}

#[derive(Debug,PartialEq)]
pub enum Ast{
    CONS(Box<Ast>,Box<Ast>),
    OR(Box<Ast>,Box<Ast>),
    ONEORMANY(Box<Ast>),
    ZEROORMANY(Box<Ast>),
    ZEROORONE(Box<Ast>),
    CHAR(char),
    DIGIT,
    LETTER,
    SPACE,
    NIL,
    ANY,
}

#[derive(Debug,Copy,Clone)]
pub enum Opcode{
    SPLIT(u32,u32),
    JMP(u32),
    CHAR(char),
    LABEL(u32),
    DIGIT,
    LETTER,
    SPACE,
    MATCH,
    ANY,
}

#[derive(Debug,Copy,Clone,PartialEq)]
pub struct MatchResult {
    pub start: usize,
    pub end: usize,
}

#[derive(Debug,Copy,Clone)]
struct MatchThread {
    ip:usize,
    pos:usize,
}

///```
/// let mut x=String::from("a");
/// let mut xs=x.chars();
/// let re = rre::parse_regex(&mut xs);
/// assert_eq!(re, Ok(Box::new(rre::Ast::CHAR('a'))));
/// ```
pub fn parse_regex(re:&mut Chars) -> Result<Box<Ast>,String>{
    let mut stack:Vec<Box<Ast>> = Vec::new();
    'outer: loop{
        match re.next(){
            Some('\\')=>{
                match re.next() {
                    Some('n') => stack.push(Box::new(Ast::CHAR('\n'))),
                    Some('r') => stack.push(Box::new(Ast::CHAR('\r'))),
                    Some('t') => stack.push(Box::new(Ast::CHAR('\t'))),
                    Some('s') => stack.push(Box::new(Ast::SPACE)),
                    Some('d') => stack.push(Box::new(Ast::DIGIT)),
                    Some('w') => stack.push(Box::new(Ast::LETTER)),
                    Some(c) => stack.push(Box::new(Ast::CHAR(c))),
                    None => break 'outer,
                }
            },
            Some('(') => {let r=parse_regex(re).expect("( error");stack.push(r);},
            Some('.') => {stack.push(Box::new(Ast::ANY));},
            Some(')') => {break 'outer;},
            Some('|') => {stack.push(Box::new(Ast::OR(Box::new(Ast::NIL),Box::new(Ast::NIL))));},
            Some('+') => {let r=stack.pop().expect("+ error");stack.push(Box::new(Ast::ONEORMANY(r)));},
            Some('*') => {let r=stack.pop().expect("* error");stack.push(Box::new(Ast::ZEROORMANY(r)));},
            Some('?') => {let r=stack.pop().expect("? error");stack.push(Box::new(Ast::ZEROORONE(r)));},
            Some(c) => {stack.push(Box::new(Ast::CHAR(c)));},
            None => break 'outer,
        }
    }
    let mut r:Box<Ast> = stack.remove(0);
    let mut stack1:Vec<Box<Ast>> = Vec::new();
    loop{
        if  stack.len() == 0 {
            break;
        }
        let   tmp:Box<Ast> = stack.remove(0);
        match *tmp {
             Ast::OR(a,b) => {stack1.push(r);stack1.push(Box::new(Ast::OR(a,b)));r=stack.remove(0);},
            _ => {r=Box::new(Ast::CONS(r,tmp));},
        }
    }
    stack1.push(r);
    loop{
        if stack1.len() == 0 {
            break;
        }
        let   tmp:Box<Ast> = stack1.remove(0);
        match *tmp {
            Ast::OR(_,_) => {let x=stack.pop().expect("| error");stack.push(Box::new(Ast::OR(x,stack1.remove(0))));},
            _ => {stack.push(tmp);},
        }
    }
    if stack.len()>1{
        return Err(String::from("regex expression error."));
    }
    return Ok(stack.remove(0));
}

pub fn compile(ast:Box<Ast>, idx:&mut u32)->Vec<Opcode>{
    let mut r:Vec<Opcode> = Vec::new();
    match *ast {
        Ast::CONS(a,b) => {
            let mut v = compile(a,idx);
            r.append(&mut v);
            let mut v = compile(b,idx);
            r.append(&mut v);
            },
        Ast::OR(a,b) => {
            let n = *idx;
            r.push(Opcode::SPLIT(n,n+1));
            r.push(Opcode::LABEL(n));
            *idx+=3;
            let mut v=compile(a,idx);
            r.append(&mut v);
            r.push(Opcode::JMP(n+2));
            r.push(Opcode::LABEL(n+1));
            let mut v=compile(b,idx);
            r.append(&mut v);
            r.push(Opcode::LABEL(n+2));
        },
        Ast::ONEORMANY(a) => {
            let n = *idx;
            r.push(Opcode::LABEL(n));
            *idx+=2;
            let mut v=compile(a,idx);
            r.append(&mut v);
            //更长匹配放后面
            r.push(Opcode::SPLIT(n+1,n));
            r.push(Opcode::LABEL(n+1));
        },
        Ast::ZEROORMANY(a) => {
            let n = *idx;
            r.push(Opcode::LABEL(n));
            //更长匹配放后面
            r.push(Opcode::SPLIT(n+2, n+1));
            r.push(Opcode::LABEL(n+1));
            *idx+=3;
            let mut v=compile(a,idx);
            r.append(&mut v);
            r.push(Opcode::JMP(n));
            r.push(Opcode::LABEL(n+2));
        },
        Ast::ZEROORONE(a) => {
            let n = *idx;
            //更长匹配放后面
            r.push(Opcode::SPLIT(n+1,n));
            r.push(Opcode::LABEL(n));
            *idx+=2;
            let mut v=compile(a,idx);
            r.append(&mut v);
            r.push(Opcode::LABEL(n+1));
        },
        Ast::CHAR(a) => {
            r.push(Opcode::CHAR(a));
        },
        Ast::DIGIT => {
            r.push(Opcode::DIGIT);
        },
        Ast::LETTER => {
            r.push(Opcode::LETTER);
        },
        Ast::ANY => {
            r.push(Opcode::ANY);
        },
        Ast::NIL => {},
        Ast::SPACE => {
            r.push(Opcode::SPACE);
        },
    }
    return r;
}

pub fn optimize(opcodes:Vec<Opcode>)->Vec<Opcode>{
    let mut r:Vec<Opcode> = Vec::new();
    let mut hm = HashMap::new();
    let mut i:u32 = 0;
    for item in opcodes.iter() {
        match item {
            Opcode::LABEL(l) => {
                hm.insert(l, i);
            },
            _=>{i+=1;},
        }
    }
    for item in opcodes.iter() {
        match item {
            Opcode::LABEL(_) => {
                
            },
            Opcode::JMP(l) => {
                r.push(Opcode::JMP(*(hm.get(l).unwrap())));
            },
            Opcode::SPLIT(l1,l2) => {
                r.push(Opcode::SPLIT(*(hm.get(l1).unwrap()) ,*(hm.get(l2).unwrap()) ));
            },
            x=>{r.push(*x);},
        }
    }
    return r;
}

pub fn compile_all(ast:Box<Ast>)->Vec<Opcode>{
    let mut idx = 0;
    let mut opcodes = compile(ast, &mut idx);
    opcodes.push(Opcode::MATCH);
    return optimize(opcodes);
}

pub fn match_string(opcodes:&Vec<Opcode>, s:&String, index:usize)->Option<MatchResult>{
    let mut threads:Vec<MatchThread> = Vec::new();
    let ss = s.as_bytes();
    threads.push(MatchThread{ip:0,pos:index});
    'outer: loop {
        if threads.len()==0{
            break 'outer;
        }
        let mut thread = threads.pop().unwrap();
        if thread.ip>=opcodes.len() {
            continue;
        }
            match opcodes[thread.ip] {
                Opcode::JMP(l) => {
                    thread.ip = l as usize;
                    threads.push(thread);
                },
                Opcode::SPLIT(l1,l2) => {
                    thread.ip = l1 as usize;
                    threads.push(thread);
                    threads.push(MatchThread{ip:l2 as usize,pos:thread.pos});
                    
                },
                Opcode::CHAR(c) => {
                  if thread.pos < ss.len()  && c == ss[thread.pos] as char {
                    thread.ip +=1;
                    thread.pos += 1;
                    threads.push(thread);
                  }
                },
                Opcode::DIGIT  => {
                    if ss[thread.pos] as char>='0' && ss[thread.pos]  as char <='9' {
                        thread.ip +=1;
                        thread.pos += 1;
                        threads.push(thread);
                    }
                },
                Opcode::LETTER  => {
                    if thread.pos < ss.len()  &&  (ss[thread.pos] as char>='a' && ss[thread.pos]  as char <='z') || ( ss[thread.pos] as char>='A' && ss[thread.pos]  as char <='Z')  {
                        thread.ip +=1;
                        thread.pos += 1;
                        threads.push(thread);
                    }
                },
                Opcode::SPACE  => {
                    if  thread.pos < ss.len()  && (ss[thread.pos] as char==' ' || ss[thread.pos]  as char =='\n'|| ss[thread.pos]  as char =='\t' || ss[thread.pos]  as char =='\r')  {
                        thread.ip +=1;
                        thread.pos += 1;
                        threads.push(thread);
                    }
                },
                Opcode::ANY  => {
                    if  thread.pos < ss.len()  {
                        thread.ip +=1;
                        thread.pos += 1;
                        threads.push(thread);
                    }
                },
                Opcode::MATCH  => {
                    let   r:MatchResult = MatchResult{start:index,end:thread.pos}; 
                    return Some(r);
                },
                _=>{},
            }

    }
    return None;
}
pub fn match_string_all(opcodes:&Vec<Opcode>, s:&String)->Option<Vec<MatchResult>>{
    let mut idx:usize=0;
    let mut r : Vec<MatchResult>= Vec::new();
    loop {
        if idx >= s.len() as usize {
            break;
        } 
        match match_string(&opcodes,&s,idx){
            Some(x) => {r.push(x);idx=x.end;},
            None => {idx += 1;},
        }
    }
    if r.len() > 0 {
        return Some(r);
    }
    return None;
}


